package me.wangshier.leetcode.easy;

import java.util.HashMap;
import java.util.Map;

/**
 * 8. 找出整型数组中占比超过一半的数
 * 这道题的核心是找到数组中出现次数超过一半的数字。以下是几种不同的解题思路：
 *
 * ### 1. 哈希表计数法
 *
 * **思路：**
 *
 * - 使用哈希表（HashMap）来记录每个数字出现的次数。
 * - 遍历数组，更新哈希表中的计数。
 * - 最后遍历哈希表，找到出现次数超过一半的数字。
 *
 * **优点：**
 *
 * - 实现简单，易于理解。
 * - 时间复杂度为O(n)，空间复杂度为O(n)。
 *
 * ### 2. 排序法
 *
 * **思路：**
 *
 * - 对数组进行排序。
 * - 由于目标数字出现次数超过一半，排序后该数字必定位于数组的中间位置。
 * - 直接返回数组中间位置的元素即可。
 *
 * **优点：**
 *
 * - 实现简单。
 * - 时间复杂度为O(n log n)，空间复杂度为O(1)（如果使用原地排序）。
 *
 * ### 3. Boyer-Moore 投票算法
 *
 * **思路：**
 *
 * - 维护一个候选数字和一个计数器。
 * - 遍历数组，如果当前数字与候选数字相同，计数器加1；否则，计数器减1。
 * - 如果计数器变为0，则更换候选数字为当前数字，并将计数器重置为1。
 * - 最终的候选数字即为出现次数超过一半的数字。
 *
 * **优点：**
 *
 * - 时间复杂度为O(n)，空间复杂度为O(1)。
 * - 效率高，且不需要额外的空间。
 *
 * ### 4. 分治法
 *
 * **思路：**
 *
 * - 将数组分成两部分，分别找到每部分的出现次数最多的数字。
 * - 递归处理，直到数组长度为1。
 * - 合并结果，比较两部分的出现次数最多的数字，选择出现次数更多的那个。
 *
 * **优点：**
 *
 * - 时间复杂度为O(n log n)，空间复杂度为O(log n)。
 * - 适用于更复杂的问题场景。
 *
 * ### 总结
 *
 * - 如果追求简单和易理解，可以选择哈希表计数法或排序法。
 * - 如果追求效率和空间优化，可以选择Boyer-Moore投票算法。
 * - 如果需要处理更复杂的问题，可以考虑分治法。
 * @Author: tongqianwen
 * @Date: 2025/3/5
 */
public class FindHalfMore {

    public static int solution(int[] array) {
        int candidate = 0;
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (count == 0) {
                candidate = array[i];
            }
            count += array[i] == candidate ? 1 : -1;
        }
        return candidate;
    }
    public static int solution1(int[] array) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : array) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > array.length / 2) {
                return entry.getKey();
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        // Add your test cases here

        System.out.println(solution(new int[]{1, 3, 8, 2, 3, 1, 3, 3, 3}) == 3);
    }
}
